package com.gofaraway.service.student.左神算法课.v2;

import com.baomidou.mybatisplus.extension.api.R;

/**
 * 二分查找
 *
 * @author ChenPeng
 * @date 2025/5/10 17:53
 */
public class 自由练习 {


    /**
     * https://leetcode.cn/problems/search-insert-position/?envType=study-plan-v2&envId=top-100-liked
     * 搜索插入位置
     * <p>
     * 给定一个排序数组和一个目标值，在数组中找到目标值，并返回其索引。如果目标值不存在于数组中，返回它将会被按顺序插入的位置。
     */
    public int searchInsert(int[] nums, int target) {

        int n = nums.length;
        int left = 0, right = n - 1, ans = n;

        while (left <= right) {
            int mid = (left + right) /2;
            if (target <= nums[mid]) {
                ans = mid;
                right = mid - 1;
            } else {
                left = mid+1;
            }
        }
        return ans;
    }


    /**
     * https://leetcode.cn/problems/trapping-rain-water/?envType=study-plan-v2&envId=top-100-liked
     * 接雨水
     * 解题思路： 先思考如何处理局部 先局部再整体
     *          对于 每个位置 i 来说，能容纳的水的体积，就是 min(L_Max, R_Max) - arr[i]
     */
    /**
     * 暴力解法
     */
    public int trap(int[] height) {
        // 判空处理，如果数组为空或长度为0，直接返回0
        if (height == null || height.length == 0) {
            return 0;
        }

        // 获取数组长度n，并初始化两个辅助数组leftMax和rightMax用于记录每个位置的左右最大高度
        int n = height.length;
        int[] leftMax = new int[n];
        int[] rightMax = new int[n];

        // 填充leftMax数组：从左往右遍历，记录当前位置i左边（包含i）的最大高度
        leftMax[0] = height[0];
        for (int i = 1; i < n; i++) {
            leftMax[i] = Math.max(leftMax[i - 1], height[i]);
        }

        // 填充rightMax数组：从右往左遍历，记录当前位置i右边（包含i）的最大高度
        rightMax[n - 1] = height[n - 1];
        for (int i = n - 2; i >= 0; i--) {
            rightMax[i] = Math.max(rightMax[i + 1], height[i]);
        }

        // 计算能接住的雨水总量
        int ans = 0;
        for (int i = 0; i < n; i++) {
            // 每个位置i能接住的雨水量 = min(左侧最高, 右侧最高) - 当前位置的高度
            ans += Math.min(leftMax[i], rightMax[i]) - height[i];
        }

        // 返回最终结果
        return ans;
    }
}
